package pers.qianyu.month_202012.date_20201226;

import java.util.*;

/**
 * [模糊]
 * 91. 最小调整代价
 * https://www.lintcode.com/problem/minimum-adjustment-cost/description
 *
 * @author mizzle rain
 * @date 2020-12-26 14:32
 */
public class MinAdjustmentCost {
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    public int minAdjustmentCost(List<Integer> A, int target) {
        int len = A.size();
        // dp[i][j]表示元素A[i]=j时，A[i]与A[i-1]差值不大于target所需要付出的最小代价
        int[][] dp = new int[len][101];
        for (int[] ints : dp) {
            for (int i = 1; i <= 100; i++) {
                ints[i] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = 1; j <= 100; j++) {
                if (i == 0) {
                    dp[0][j] = Math.abs(j - A.get(0));
                } else {
                    int left = Math.max(1, j - target);
                    int right = Math.min(100, j + target);
                    int abs = Math.abs(j - A.get(i));
                    for (int k = left; k <= right; k++) {
                        dp[i][j] = Math.min(dp[i][j], abs + dp[i - 1][k]);
                    }
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= 100; i++) {
            ans = Math.min(ans, dp[len - 1][i]);
        }
        return ans;
    }
}
